package dp.base;

import java.util.Arrays;

public class Solution_322 {

    int[][] memo;

    /**
     * 比较套路，但是容易把边界条件i<0写成i==0
     */
    public int coinChange(int[] coins, int amount) {
        int m = coins.length + 1;
        memo = new int[m][amount + 1];
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i], -1);
        }
        int res = dfs(coins.length - 1, amount, coins);
        if (res >= Integer.MAX_VALUE / 2)
            return -1;
        return res;
    }

    private int dfs(int i, int j, int[] coins) {
        if (i < 0) {
            if (j == 0)
                return 0;
            return Integer.MAX_VALUE / 2;
        }
        if (memo[i][j] != -1)
            return memo[i][j];
        if (coins[i] > j)
            return memo[i][j] = dfs(i - 1, j, coins);
        return memo[i][j] = Math.min(dfs(i - 1, j, coins), dfs(i, j - coins[i], coins) + 1);
    }
}
